\contentsline {chapter}{Statement of Originality}{v}
\contentsline {chapter}{Acknowledgments}{vii}
\contentsline {chapter}{Abstract}{ix}
\contentsline {chapter}{List of Figures}{xiii}
\contentsline {chapter}{List of Tables}{xv}
\contentsline {chapter}{List of Algorithms}{xvii}
\contentsline {chapter}{\numberline {1}Introduction}{1}
\contentsline {section}{\numberline {1.1}Tree Comparison}{1}
\contentsline {section}{\numberline {1.2}Tree Distance Metric}{1}
\contentsline {section}{\numberline {1.3}The Problem}{2}
\contentsline {section}{\numberline {1.4}Organisation}{3}
\contentsline {chapter}{\numberline {2}Operations}{5}
\contentsline {section}{\numberline {2.1}Relabel}{5}
\contentsline {section}{\numberline {2.2}Delete}{5}
\contentsline {section}{\numberline {2.3}Insert}{6}
\contentsline {section}{\numberline {2.4}Rotation}{7}
\contentsline {section}{\numberline {2.5}Switch}{7}
\contentsline {chapter}{\numberline {3}Algorithms}{9}
\contentsline {section}{\numberline {3.1}Tree Edit Distance}{9}
\contentsline {subsection}{\numberline {3.1.1}Tai Algorithm}{9}
\contentsline {subsection}{\numberline {3.1.2}Zhang \& Shashas' Algorithm}{11}
\contentsline {section}{\numberline {3.2}Tree Alignment Distance}{12}
\contentsline {section}{\numberline {3.3}Tree Rotation Distance}{13}
\contentsline {subsection}{\numberline {3.3.1}Rotation Distance}{13}
\contentsline {subsection}{\numberline {3.3.2}Tree Rotation Distance}{14}
\contentsline {chapter}{\numberline {4}Proposed Approach}{23}
\contentsline {section}{\numberline {4.1}Model}{23}
\contentsline {section}{\numberline {4.2}Algorithm}{24}
\contentsline {section}{\numberline {4.3}Rotation Distance}{25}
\contentsline {section}{\numberline {4.4}Error}{25}
\contentsline {subsection}{\numberline {4.4.1}Mean Absolute Error}{25}
\contentsline {subsection}{\numberline {4.4.2}Mean Square Error}{26}
\contentsline {chapter}{\numberline {5}Experiments and Results}{27}
\contentsline {section}{\numberline {5.1}Experiment 1 Determine Best Cost Function}{27}
\contentsline {section}{\numberline {5.2}Experiment 2 Randomly Generated Ordered Trees}{29}
\contentsline {section}{\numberline {5.3}Experiment 3 Randomly Generated Unorder Trees}{30}
\contentsline {chapter}{\numberline {6}Conclusions}{31}
\contentsline {chapter}{\numberline {7}Future Work}{32}
\contentsline {chapter}{Bibliography}{32}
\contentsline {part}{Appendices}{37}
\contentsline {chapter}{\numberline {A}Program listings}{38}
\contentsline {section}{\numberline {A.1}Node}{38}
\contentsline {section}{\numberline {A.2}Tree}{41}
\contentsline {section}{\numberline {A.3}TED Tree}{42}
\contentsline {section}{\numberline {A.4}Model}{46}
\contentsline {section}{\numberline {A.5}Generate Tree}{49}
\contentsline {section}{\numberline {A.6}Rotation Distance Ordered}{55}
\contentsline {section}{\numberline {A.7}Rotation Distance Unordered}{59}
\contentsline {section}{\numberline {A.8}JSON Parser}{63}
\contentsline {section}{\numberline {A.9}Program}{68}
\contentsline {section}{\numberline {A.10}Classifier}{70}
\contentsline {section}{\numberline {A.11}Display Tree}{70}
\contentsline {section}{\numberline {A.12}Run Process}{71}
